package com.example.interview.bean.tree.bst;

import com.alibaba.fastjson.JSON;
import lombok.Data;

/**
 * @author ：superdyf
 * @date ：Created in 2021/10/14 16:12
 * @description：
 * @modified By：
 */
@Data
public class BST<E extends Comparable<E>> {
    private Node<E> root;
    interface Select<E>{
        void  pre(E e);
        void  inorder(E e);
        void  post(E e);
    }
    @Data
    static class Node<E extends Comparable<E>>{
        private E e;
        private Node<E> left;
        private Node<E> right;

        public Node(E e) {
            this.e = e;
        }
        /**
         * @Author superdyf
         * @Description //TODO 递归
         * @Date 17:15 2021/10/14
         * @Param [root, e]
         * @return com.example.interview.bean.tree.bst.BST.Node<E>
         **/
        public void addV(Node<E> root,Node<E> e){
           Node<E> current;
            boolean l=root.getE().compareTo(e.getE())>0;
            if(l){
                if((current=root.getLeft())==null){
                    root.setLeft(e);
                    return;
                }
            }else{
                if((current=root.getRight())==null){
                    root.setRight(e);
                    return;
                }
            }
            addV(current,e);
        }
        public Node<E>  addR(Node<E> root,Node<E> e){
            if(null==root){
                return e;
            }
            if(root.getE().compareTo(e.getE())>0){
                root.setLeft(addR(root.getLeft(),e));
            }else{
                root.setRight(addR(root.getRight(),e));
            }
            return root;
        }
        public void iter(Node<E> root,Select<E> select){
            if(null==root){
                return;
            }
//            System.out.print(print(root,"pre:"));
            select.pre(root.getE());
            iter(root.getLeft(),select);
            select.inorder(root.getE());
//            System.out.print(print(root,"inorder:"));
            iter(root.getRight(),select);
            select.post(root.getE());
//            System.out.print(print(root,"post:"));
        }
        /**
         * @Author superdyf
         * @Description //TODO 迭代
         * @Date 17:39 2021/10/14
         * @Param [e]
         * @return void
         **/
        public void add(E e){
            Node<E> newNode=new Node<>(e),parent,current=this;
            for(;;){
                parent=current;
                if(parent.getE().compareTo(newNode.getE())>0){
                    if((current=current.getLeft())==null){
                        parent.setLeft(newNode);
                        return ;
                    }
                }else{
                    if((current=current.getRight())==null){
                        parent.setRight(newNode);
                        return ;
                    }
                }
            }
        }
    }

    public BST(Node<E> root) {
        this.root = root;
    }
    public BST(E e) {
        this.root = new Node<>(e);
    }
    public BST() {
    }
    public void add(E e){
        root.addV(root,new Node<>(e));
    }
    public void addI(E e){
        root.add(e);
    }
    public static <E extends Comparable<E>> String print(Node<E> e, String d){
        return null==e?d:d+":"+e.getE();
    }
    public static void main(String[] args) {
        Node<String> n=new Node<>("s");
        String s="商贷放款理解为何我尽快发货了交换空间序号总局和请叫我是拉锯孙女士";
        BST<String> bst=new BST<>("s");
        for (char c : s.toCharArray()) {
            bst.add(String.valueOf(c));
//            bst.add(String.valueOf(c));
//            bst.addI(String.valueOf(c));
        }
        System.out.println(JSON.toJSONString(bst.root));
        bst.root.iter(bst.root, new Select<String>() {
            @Override
            public void pre(String s) {
                System.out.println("pre:"+s);
            }

            @Override
            public void inorder(String s) {
                System.out.println("inorder:"+s);
            }

            @Override
            public void post(String s) {
                System.out.println("post:"+s);
            }
        });
    }
}
